import java.util.Arrays;
import java.util.Comparator;

/**
 * @author VernHe
 * @date 2021年08月26日 15:23
 */
public class Solution_0416 {
    public static void main(String[] args) {
//        int[] nums = new int[]{1, 5, 11, 5};
//        int[] nums = new int[]{1, 2, 3, 5};
        int[] nums = new int[]{1, 1};
//        System.out.println(new Solution_0416().canPartition(nums));
    }
    /*public boolean canPartition(int[] nums) {
        // 排序，计算总和
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        for (int i = 0; i < nums.length; i++) {
            if (search(0, target, i,nums)) {
                return true;
            }
        }
        return false;
    }

    *//**
     *
     * @param cur       当前和的值
     * @param target    目标值
     * @param index     当前下标
     * @param nums      数组
     * @return          是否存在
     *//*
    private boolean search(int cur, int target, int index, int[] nums) {
        // 递归基
        if (index == nums.length) {
            return false;
        }
        int sum = cur + nums[index];
        if (sum > target) {
            return false;
        }
        if (sum == target) {
            return true;
        }
        // 从下一个位置开始继续找
        for (int i = index + 1; i < nums.length; i++) {
            if (search(sum, target, i, nums)) {
                // 找到了就返回true，否则返回false
                return true;
            }
        }
        return false;
    }*/

    public boolean canPartition(int[] nums) {
        // 求和
        int len = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum & 1) == 1) {
            return false;
        }
        int target = sum >> 1;
        // [0,target]
        // dp[i][j] 表示在第[0,i]范围内的数是否能刚好装满容量为j的口袋
        boolean[][] dp = new boolean[len][target + 1];
        // 初始化第一行
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        // 从第二行开始遍历
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                // 复制上一行的
                dp[i][j] = dp[i-1][j];
                // 此时如果就只用当前一个就可以装满
                if (nums[i] == j) {
                    dp[i][j] = true;
                }
                // 如果只靠当前这一个无法装满
                if (nums[i] < j) {
                    // 之前就已经装满了或者加了这个后才装满
                    dp[i][j] = dp[i-1][j] || dp[i - 1][j - nums[i]];
                }
            }
            if (dp[i][target]) {
                return true;
            }
        }
        return dp[len - 1][target];
    }
}
